/*
 * @lc app=leetcode.cn id=19 lang=cpp
 *
 * [19] 删除链表的倒数第 N 个结点
 *
 * https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/description/
 *
 * algorithms
 * Medium (43.67%)
 * Likes:    1904
 * Dislikes: 0
 * Total Accepted:    713.2K
 * Total Submissions: 1.6M
 * Testcase Example:  '[1,2,3,4,5]\n2'
 *
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：head = [1,2,3,4,5], n = 2
 * 输出：[1,2,3,5]
 *
 *
 * 示例 2：
 *
 *
 * 输入：head = [1], n = 1
 * 输出：[]
 *
 *
 * 示例 3：
 *
 *
 * 输入：head = [1,2], n = 1
 * 输出：[1]
 *
 *
 *
 *
 * 提示：
 *
 *
 * 链表中结点的数目为 sz
 * 1 <= sz <= 30
 * 0 <= Node.val <= 100
 * 1 <= n <= sz
 *
 *
 *
 *
 * 进阶：你能尝试使用一趟扫描实现吗？
 *
 */

// @lc code=start
#include <iostream>
#include <unordered_map>
using namespace std;
//  Definition for singly-linked list.
/* struct ListNode {
     int val;
     ListNode *next;
     ListNode() : val(0), next(nullptr) {}
     ListNode(int x) : val(x), next(nullptr) {}
     ListNode(int x, ListNode *next) : val(x), next(next) {}
 }; */

class Solution
{
public:
    ListNode *removeNthFromEnd(ListNode *head, int n)
    {
        ListNode *fast = head;
        ListNode *slow = head;
        unordered_map<int, ListNode *> hashmap;
        hashmap[0] = head;
        int cnt = 0;
        int amount = 0;
        while (fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
            cnt++;
            hashmap[cnt] = slow;
        }
        if (fast)
        {
            amount = 2 * cnt + 1;
        }
        else
        {
            amount = 2 * cnt;
        }
        if (amount == 1)
        {
            return nullptr;
        }
        else
        {
            // amount-n为要删除节点的下标
            while (cnt < (amount - n - 1))
            {
                slow = slow->next;
                cnt++;
            }
            // 此时slow处于要删除节点的前一个节点
            if (cnt == (amount - n - 1))
            {
                ListNode *deleteNode = slow->next;
                slow->next = deleteNode->next;
                delete (deleteNode);
                return head;
            }
            if (cnt >= (amount - n))
            {
                if (amount - n == 0)
                {
                    ListNode *first = head;
                    head = head->next;
                    delete (first);
                    return head;
                }
                else
                {
                    ListNode *predeleteNode = hashmap[amount - n - 1];
                    ListNode *deleteNode = predeleteNode->next;
                    predeleteNode->next = deleteNode->next;
                    delete (deleteNode);
                    return head;
                }
            }
        }
        return head;
    }
};
// @lc code=end
